package j2024.j202408;

import java.util.ArrayList;
import java.util.List;

public class j0831 {
    int[] dx={0,0,-1,1};
    int[] dy={1,-1,0,0};
    int m,n;

    /**
     * 130. 被围绕的区域
     * @param board
     */
    public void solve(char[][] board) {
        m = board.length;n = board[0].length;
        for (int i = 0; i < m; i++) {
            if(board[i][0]=='O'){
                dfs(board,i,0);
            }
            if(board[i][n-1]=='O'){
                dfs(board,i,n-1);
            }
        }
        for (int i = 0; i < n; i++) {
            if(board[0][i]=='O'){
                dfs(board,0,i);
            }
            if(board[m-1][i]=='O'){
                dfs(board,m-1,i);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j]=='.'){
                    board[i][j]='O';
                }else if(board[i][j]=='O'){
                    board[i][j] = 'X';
                }
            }
        }
    }
    public void dfs(char[][] board,int i,int j){
        board[i][j] = '.';
        for (int k = 0; k < 4; k++) {
            int x = i+dx[k],y = j+dy[k];
            if(x>=0 && x<m  && y>=0 && y<n && board[x][y]=='O'){
                dfs(board,x,y);
            }
        }
    }
}
class l2{
    int[] dx={0,0,-1,1};
    int[] dy={1,-1,0,0};
    int m,n;

    /**
     * 417. 太平洋大西洋水流问题
     * @param heights
     * @return
     */
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
         m = heights.length;n = heights[0].length;
        boolean[][] Pac = new boolean[m][n],Atl = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(heights,i,0,Pac);
            dfs(heights,i,n-1,Atl);
        }
        for (int i = 0; i < n; i++) {
            dfs(heights,0,i,Pac);
            dfs(heights,m-1,i,Atl);
        }
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(Pac[i][j] && Atl[i][j]){
                    List<Integer> tmp  = new ArrayList<>();
                    tmp.add(i);tmp.add(j);
                    ret.add(tmp);
                }
            }
        }
        return ret;
    }
    public void dfs(int[][] heights,int i,int j,boolean[][] vis){
        vis[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k],y = j + dy[k];
            if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && heights[x][y]>=heights[i][j]){
                dfs(heights,x,y,vis);
            }
        }
    }
}
class l3{
    int[] dx = {0,0,-1,1,-1,-1,1,1};
    int[] dy = {1,-1,0,0,-1,1,-1,1};
    int m,n;

    /**
     * 529. 扫雷游戏
     * @param board
     * @param click
     * @return
     */
    public char[][] updateBoard(char[][] board, int[] click) {
        m = board.length;n = board[0].length;
        int x = click[0],y = click[1];
        if(board[x][y]=='M'){
            board[x][y] = 'X';
            return board;
        }
        dfs(board,x,y);
        return board;
    }
    public void dfs(char[][] board,int i,int j){
        //统计周围地雷个数
        int count = 0;
        for (int k = 0; k < 8; k++) {
            int x = i+dx[k],y = j+dy[k];
            if(x>=0 && x<m  && y>=0 && y<n && board[x][y]=='M'){
                count++;
            }
        }
        if(count==0){
            board[i][j]='B';
            for (int k = 0; k < 8; k++) {
                int x = i+dx[k],y = j+dy[k];
                if(x>=0 && x<m  && y>=0 && y<n && board[x][y]=='E'){
                    dfs(board,x,y);
                }
            }
        }else {
            board[i][j] = (char)('0'+count);
            return;
        }
    }
}
